# !/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
===========================
@Time : 2022/8/21 0021 12:38
@Author : 测试开发工程师
@File : 4. 堆栈.py
@Software: PyCharm
============================
"""

"""
堆栈： 数组-顺序栈 ， 链表-链式栈
    入栈 -> 函数调用  ->  出栈   ： 先入后出
    编译原理：语法分析
    括号匹配

"""


# 顺序栈

class ArrayStack:

    def __init__(self, n) -> None:
        self.data = [-1] * n
        self.n = n
        self.count = 0

    # 入栈
    def push(self, value):
        if self.n == self.count:
            return False
        self.data[self.count] = value
        self.count += 1
        return True

    # 出栈
    def pop(self):
        if self.count == 0:
            return None
        self.count -= 1
        return self.data[self.count]


def test_static():
    array_stack = ArrayStack(5)
    data = ['a', 'b', 'c', 'd', 'e']
    for i in data:
        array_stack.push(i)

    result = array_stack.push('a')
    assert not result
    data.reverse()
    for i in data:
        assert i == array_stack.pop()

    assert array_stack.pop() is None


if __name__ == '__main__':
    test_static()


# 链式栈
class StackBaseOnlinkedList:

    def __init__(self) -> None:
        self.top = None

    # 入栈
    def push(self, value):
        new_node = self.Node(value)
        if self.top is None:
            self.top = new_node
        else:
            new_node.next = self.top
            self.top = new_node

    # 出栈
    def pop(self):
        if self.top is None:
            return -1
        result = self.top.data
        self.top = self.top.next
        return result

    class Node:
        def __init__(self, data) -> None:
            self.data = data
            self.next = None


def test_static(self):
    stack = StackBaseOnlinkedList()
    data = [1, 2, 3, 4, 5]
    for i in data:
        stack.push(i)
    data.reverse()
    for i in data:
        assert i == stack.pop()
